The present invention relates to a protocol validation system which receives a communication protocol specification, and detects an error in said specification.
A software system used in an electronic exchange system and/or a communication processing system has become complicated, following the latest development of communication technology. Therefore, the high productivity of producing a communication software is substantial.
One of the important means for enhancing productivity of a communication software is to define clearly the requested specification of a communication software, at early stage of study, so that no request fed back to a software designer happens.
A protocal which defines signal formats and/or procedure for transmission and/or reception of a signal through a communication line is one of the important softwares in communication. Therefore, when there is an error in a protocol, it is preferable that an automatic detection of that error is established.
Conventionally, a protocol validation has been accomplished by enumerating and testing all the combinations of the operation and the state of a communication system defined by the protocol.
A prior system is described in accordance with FIGS. 2 and 3.
FIG. 2 shows a protocol to be tested, and has a communication system with a process 1, a process 2 and a process 3. A process 1 and a process 3 may be a terminal apparatus, or a process 2 may be an exchange system, or all the processes 1, 2 and 3 may be included in a single CPU. A process performs a signal transmission and/or a signal reception between other processes of different function, and a communication system comprises a plurality of processes. FIG. 2 is an example of a protocol which has three processes.
In FIG. 2, a circle shows a state, and an arrow shows a transition. A label attached to an arrow shows a transmission or a reception of a signal. In general, -a.sub.j.sup.i shows a transmission of a signal (a) from the process (i) to the process (j), and +a.sub.j.sup.i shows a reception of a signal (a) from the process (i) to the process (j). Therefore, it is understood that the process 1 has the initial state A.sub.1, changes the state to B.sub.1 when it sends a signal (1) to the process 2, changes the state to C.sub.1 when it receives the signal (2) from the process 2, and returns to the initial state A.sub.1 when it sends the signal (3) to the process 3. Although an operation of a process itself is simple, it is difficult to find a logical error in operation between each of the processes.
Conventionally, a state transition chart which includes all the operation of a communication system is prepared, and finds a logical error in preparation of said chart. FIG. 3 shows a result of a prior test for the protocol of FIG. 2. FIG. 3 is called a global transition chart, since it shows all the system transitions of the system. A state of each process is shown in a circle, and that state is called a global state.
First, an executable transition in the initial global status (A.sub.1, A.sub.2, A.sub.3) is -1.sub.2.sup.1 in the process 1, and -2.sub.1.sup.2 in the process 2. The process 3 is unexecutable, since all the transitions are reception, and the signal 3 and the signal 4 are not sent from any process. Therefore, the transition -1.sub.2.sup.1 is first tested, and the global state (B.sub.1, A.sub.2, A.sub.3) is obtained. The immediately executable transition on that state is then detected, and +1.sub.2.sup.1 and -2.sub.1.sup.2 are found. The +1.sub.2.sup.1 goes to the global state (B.sub.1, C.sub.2, A.sub.3), at which the immediately executable transition is only -4.sub.3.sup.2, and the global state (B.sub.1, B.sub.2, A.sub.3) is obtained. Next, the process 3 receives the signal 4, and the global state changes to (B.sub.1, B.sub.2, C.sub.3) However, no transition is executable at that state. That is to say, although the state (B.sub.1) of the process 1 can receive the signal (2), the signal (2) is not sent from the process 2 before that state, therefore, it is unexecutable. Further, at the state (B.sub.2) of the process 2, although the signal 1 may be received, the signal 1 from the process 1 has already been handled when the global state (B.sub.1, A.sub.2, A.sub.3) changes to (B.sub.1, C.sub.2, A.sub.3), and further, at the state C.sub.3 of the process 3, although the signal 5 can be received, the signal 5 has not been sent from any process before the global state (B.sub.1, B.sub.2, C.sub.3). Therefore, the global state (B.sub.1, B.sub.2, C.sub.3) has no executable transition. That state is called a deadlock state. One of the objects of a protocol validity system is to find a deadlock state.
It is noted that FIG. 3 includes all the executable transitions, therefore, a transition which is not included in FIG. 3 but included in FIG. 2 is redundant. Therefore, it is found that the state (C.sub.3) in the process 3 has the redundant signal reception +5.sub.3.sup.1.
At the global state (A.sub.1, B.sub.2, A.sub.3) in FIG. 3, the immediate executable transition is only -1.sub.2.sup.1. However, the signal 2 is sent from the process 2 to the process 1. Accordingly, the reception transition +2.sub.1.sup.2 must be possible at the global state (A.sub.1, B.sub.2, A.sub.3). That transition is not defined in the protocol of FIG. 2, and is detected as the unspecified reception. Similarly, the unspecified reception +6.sub.2.sup.3 at the global transition (A.sub.1, B.sub.2, D.sub.3) is found.
As described above, a protocol is tested by executing all the executable transitions starting from the initial global state (A.sub.1, A.sub.2, A.sub.3).
However, a prior protocol validity system thus described has the disadvantage that a large amount of handling time makes impossible the validity test, when a protocol is large and complicated with many states and transitions, since it handles all the executable transitions. In particular, it is almost impossible to implement the system reasonably in a hardware device, since a large capacity of memory is required for storing the global state transition chart. Therefore, no hardware implementation has been found.